package BinaryTree;

// 从中序与后序遍历序列构造二叉树:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
         this.right = right;
      }
  }
public class Solution {
    public int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index=postorder.length-1;
        return buildTreeChild (inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild (int[] inorder, int[] postorder,int ibegin,int iend) {
        if(ibegin>iend){
            return null;
        }
         // 先实例化 根节点
        TreeNode root=new TreeNode(postorder[index]);
        
        // 从中序遍历中找到根节点
        int n=findIndex(inorder,ibegin,iend,postorder[index]);
        if(n == -1){
            return null;
        }
        index--;
        root.right=buildTreeChild (inorder,postorder,n+1,iend);
        root.left=buildTreeChild (inorder,postorder,ibegin,n-1);
        

        return root;
    }

    // 从中序遍历 中 找到 前序遍历中 的节点
    public int findIndex(int[] inorder,int ibegin,int iend,int key){
        for(int i=ibegin;i<=iend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        // 没找到
        return -1;
    }
}